{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 方法一：用字符串\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if(n <= 0):\n",
    "            return [0]\n",
    "        result = []\n",
    "        selected = set()\n",
    "        s = ['0'] * n\n",
    "        s[0] = '1' #保证从零开始\n",
    "        def Fun():\n",
    "            for i in range(n):\n",
    "                c = s[i]\n",
    "                if(c == '0'):\n",
    "                    s[i] = '1'\n",
    "                else:\n",
    "                    s[i] = '0'\n",
    "                x = int(''.join(s), 2)\n",
    "                if(x not in selected):\n",
    "                    selected.add(x)\n",
    "                    result.append(x)\n",
    "                    Fun()\n",
    "                    break\n",
    "                else:\n",
    "                    s[i] = c\n",
    "        Fun()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "#方法二：用位运算(更优)\n",
    "#\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        if(n <= 0):\n",
    "            return [0]\n",
    "        result = []\n",
    "        selected = set()\n",
    "        candidates = [(2**x) for x in range(n)]\n",
    "        curr = 1\n",
    "        flag = True\n",
    "        while(flag):\n",
    "            flag = False\n",
    "            for i in candidates:\n",
    "                temp = curr ^ i\n",
    "                if( temp not in selected):\n",
    "                    selected.add(temp)\n",
    "                    result.append(temp)\n",
    "                    curr = temp\n",
    "                    flag = True\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "#方法二：用位运算(更优)\n",
    "#\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        return [i ^ (i >> 1)  for i in range(2 ** n)]\n",
    "        '''\n",
    "        关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);\n",
    "        如 n = 3: \n",
    "        G(0) = 000, \n",
    "        G(1) = 1 ^ 0 = 001 ^ 000 = 001\n",
    "        G(2) = 2 ^ 1 = 010 ^ 001 = 011 \n",
    "        G(3) = 3 ^ 1 = 011 ^ 001 = 010\n",
    "        G(4) = 4 ^ 2 = 100 ^ 010 = 110\n",
    "        G(5) = 5 ^ 2 = 101 ^ 010 = 111\n",
    "        G(6) = 6 ^ 3 = 110 ^ 011 = 101\n",
    "        G(7) = 7 ^ 3 = 111 ^ 011 = 100\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "#方法三：动态规划（归纳）\n",
    "#\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            e = 2**i\n",
    "            result = result + [x+e for x in result[::-1]]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]\n"
     ]
    }
   ],
   "source": [
    "a = Solution()\n",
    "print(a.grayCode(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>1. 分析</h2>\n",
    " 这道题本质上是道动态规划题目，\n",
    " \n",
    " 根据格雷编码的定义：\n",
    "\n",
    " 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。\n",
    "\n",
    " 我们可以知道，数字n-1的格雷编码同时也可以作为数字n的格雷编码的一部分.\n",
    " \n",
    " 而且数字n-1的格雷编码的个数为2^(n-1)个，所以要找到数字n的格雷编码只需要再找到2^(n-1)个即可。\n",
    "\n",
    " -对于这另外一半的求法, 一种方法是通过对前一半（即n-1的格雷编码）的编码的首位加1得到：\n",
    "\n",
    "\n",
    "\n",
    "<p align=\"center\"><img width=400px src=\"https://pic.leetcode-cn.com/3dac46794f63bd7a01482137a79e00596010e40f8e6c309690c98c28c5321b7a-image.png\" alt=\"image.png\" ></p>\n",
    "\n",
    "\n",
    "\n",
    "<h2>2. DP推导</h2>\n",
    "<p>我们定义数字n的格雷编码为<code>dp[n]</code>, 期中<code>dp[n][i]</code>为n的格雷编码的第i个，显然dp要是个二维数组，而且每一行的个数还不一样。dp[n]中i的范围为 : <code>[0, 2^n)</code>, 我们定义<code>N</code>为数字n的格雷编码的总个数.</p>\n",
    "<p><strong>状态转移方程:</strong></p>\n",
    "<pre><button class=\"md-btn-copy\" title=\"复制代码\"><i></i></button>\n",
    "<code><span class=\"hljs-code\">            dp[n-1][i]         (0 &lt;= i &lt; N/2)</span>\n",
    "dp[<span class=\"hljs-string\">n</span>][<span class=\"hljs-symbol\">i</span>] = \n",
    "<span class=\"hljs-code\">            dp[n][N - 1 - i]   (N/2 &lt;= i &lt; N)</span>\n",
    "</code></pre>\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
